/*
 * CCVisu is a tool for visual graph clustering
 * and general force-directed graph layout.
 * This file is part of CCVisu.
 *
 * Copyright (C) 2005-2011  Dirk Beyer
 *
 * CCVisu is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * CCVisu is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with CCVisu; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Please find the GNU Lesser General Public License in file
 * license_lgpl.txt or http://www.gnu.org/licenses/lgpl.txt
 *
 * Dirk Beyer    (firstname.lastname@uni-passau.de)
 * University of Passau, Bavaria, Germany
 */
package org.sosy_lab.ccvisu.clustering;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

import org.sosy_lab.ccvisu.graph.GraphData;
import org.sosy_lab.ccvisu.graph.GraphVertex;
import org.sosy_lab.ccvisu.graph.Group;
import org.sosy_lab.ccvisu.graph.Group.GroupKind;
import org.sosy_lab.common.LogManager;
import org.sosy_lab.util.Stopwatch;

/**
 * Implementation of a clustering algorithm based on
 * @see ccvisu.clustering.ClustererMinDist
 * with some heuristics that enhance performance.
 */
public class BuggyMinDistClusterer extends ClustererMinDist {

  /**
   * Put all nodes with a distance of at most n percent
   * of the diagonal of the layout in one cluster.
   * Heuristic that helps to minimize execution time of the algorithm.
   * A good value is 0.05
   */
  protected final double maxDistancePercentToAutoMerge;

  /**
   * Stop creating clusters of the graph after all clusters
   * have a certain distance (percent of the diagonal of the layout). */
  protected final double maxDistancePercentUntilStopMerge;

  /**
   * Constructor.
   *
   * @param graph  Graph that should be clustered.
   * @param numberOfClusters   Number of partitions hat should be found at least.
   * @param maxDistancePercentToAutoMerge  @see ClustererMinDistPerc#maxDistancePercentToAutoMerge
   * @param maxDistancePercentUntilStopMerge @see ClustererMinDistPerc#maxDistancePercentUntilStopMerge
   */
  public BuggyMinDistClusterer(GraphData graph, LogManager logger,
      int numberOfClusters, double maxDistancePercentToAutoMerge,
      double maxDistancePercentUntilStopMerge) {

    super(graph, logger, numberOfClusters);

    this.maxDistancePercentToAutoMerge = maxDistancePercentToAutoMerge;
    this.maxDistancePercentUntilStopMerge = maxDistancePercentUntilStopMerge;
  }

  /**
   * @see ccvisu.AbstractClusterer#internalCreateClustersOfLayout(ccvisu.GraphData, int)
   */
  @Override
  public List<Group> internalCreateClustersOfLayout() throws InterruptedException {
    Stopwatch sw = Stopwatch.createAndStart();

    List<Group> clusters = new ArrayList<Group>();
    List<GraphVertex> vertices = graphData.getVertices();

    //
    // Initially put each node in a separate cluster.
    //
    setProgress(0, vertices.size(), "Creating initial clusters.");

    double maxY = Double.MIN_VALUE;
    double minY = Double.MAX_VALUE;
    double minZ = Double.MAX_VALUE;
    double maxZ = Double.MIN_VALUE;
    double maxX = Double.MIN_VALUE;
    double minX = Double.MAX_VALUE;

    int clusterSeqNo = 0;
    for (GraphVertex v : vertices) {
      Group vertexCluster = new Group("Cluster " + clusterSeqNo++, graphData);
      vertexCluster.setKind(GroupKind.CLUSTER);
      vertexCluster.addNode(v);
      clusters.add(vertexCluster);

      maxX = Math.max(maxX, v.getPosition().getX());
      maxY = Math.max(maxY, v.getPosition().getY());
      maxZ = Math.max(maxZ, v.getPosition().getZ());

      minX = Math.min(maxX, v.getPosition().getX());
      minY = Math.min(maxY, v.getPosition().getY());
      minZ = Math.min(maxZ, v.getPosition().getZ());
    }

    double layoutDiagonal = Math.sqrt(Math.abs(maxX - minX) * Math.abs(maxX - minX)
      + Math.abs(maxZ - minZ) * Math.abs(maxZ - minZ)
      + Math.abs(maxY - minY) * Math.abs(maxY - minY));

    System.out.println("Max vertex distance: " + layoutDiagonal);

    //
    // Calculate the parameters.
    //
    int initialNumOfClusters = clusters.size();
    double maxDistanceToAutoMerge = layoutDiagonal * maxDistancePercentToAutoMerge;
    double maxDistanceUntilStopMerge = layoutDiagonal * maxDistancePercentUntilStopMerge;

    //
    // Aggregate cluster until there are only k clusters left.
    //
    boolean needMoreClusterMerging = true;
    while (needMoreClusterMerging) {
      int numOfClustersBeforeIteration = clusters.size();

      setProgress(initialNumOfClusters - numOfClustersBeforeIteration, initialNumOfClusters, "Creating clusters");
      System.out.println("Num of non-empty clusters: " + numOfClustersBeforeIteration);

      // Calculate the distance between all clusters.
      // Merge clusters if their distance is less than lMaxDistanceToAutoMerge.
      PriorityQueue<ClusterPair> lSecondStageCluster = new PriorityQueue<ClusterPair>();
      for (int a = clusters.size() - 1; a >= 0; a--) {
        Group clusterA = clusters.get(a);

        if (Thread.interrupted()) { throw new InterruptedException(); }

        for (int b = a - 1; b >= 0; b--) {
          Group clusterB = clusters.get(b);

          ClusterPair lPair = new ClusterPair(clusterA, clusterB, null, null);
          double lPairDistance = lPair.getEucDistanceBetweenBarycenters();

          // First stage merging:
          //    Merge clusters without recalculating the distances to the
          //    merged clusters.
          // * Only merge clusters having a distance less than...
          if (lPairDistance < maxDistanceUntilStopMerge) {
            // * Merge all clusters within a certain distance...
            if (lPairDistance < maxDistanceToAutoMerge) {
              // Merge the pair of clusters with the smallest distance.
              mergeClusters(lPair.clusterA, lPair.clusterB);
              clusters.remove(a);
              break;
            } else {
              // Hint: lSecondStageCluster is a heap!
              lSecondStageCluster.add(lPair);
            }
          }
        }
      }

      if (lSecondStageCluster.size() > 0) {
        // Merge the pair of Clusters with the shortest distance.
        // No sorting of lSecondStageCluster is required because it is a heap.
        ClusterPair lPair = (ClusterPair) lSecondStageCluster.peek();
        double lPairDistance = lPair.getEucDistanceBetweenBarycenters();
        if (lPairDistance < maxDistanceUntilStopMerge) {
          // Important: Merge to the not empty cluster!
          Group sourceGroup = lPair.clusterA;
          Group targetGroup = lPair.clusterB;
          if (targetGroup.getNodes().size() == 0) {
            sourceGroup = lPair.clusterB;
            targetGroup = lPair.clusterA;
          }

          mergeClusters(sourceGroup, targetGroup);
          clusters.remove(sourceGroup);
        }
      }

      // More merging of clusters necessary?
      needMoreClusterMerging = (clusters.size() > numberOfClusters) //<-- Still more clusters than desired.
      &&  (numOfClustersBeforeIteration != clusters.size()); //<-- Merge of clusters still possible.
    }

    setProgress(1, 1, sw.stop().toString());

    return clusters;
  }

}
